package leetcode_day._2023._12;

/**
 * 1901.寻找峰值 II
 * 算法：二分查找 + 贪心
 *
 * @author yezh
 * @date 2023/12/19 15:56
 */
public class _19 {

    public int[] findPeakGrid(int[][] mat) {
        int m = mat.length, l = 0, r = m - 1;
        if (m > 1) {
            while (l < r) {
                int mid = l + (r - l + 1) / 2;
                int idx = maxPeak(mat[mid]);
                // 只要 m > 1, 当 mid = 0 时, 此时 l = 0, r = 0, 肯定不会走到这步, 所以 mid - 1 肯定 >= 0
                if (mat[mid][idx] > mat[mid - 1][idx]) l = mid;
                else r = mid - 1;
            }
        }
        return new int[]{l, maxPeak(mat[l])};
    }

    int maxPeak(int[] nums) {
        int maxIdx = -1, n = nums.length;
        for (int i = 0; i < n; i++)
            if ((i == 0 || nums[i] > nums[i - 1]) && (i == n - 1 || nums[i] > nums[i + 1]))
                maxIdx = maxIdx == -1 ? i : nums[i] > nums[maxIdx] ? i : maxIdx;
        return maxIdx;
    }

}
